#include "GraphKind.h"
#include "infotype.h"
#include <functional>
#include <QQueue>
#ifndef ALGRAPH_H
#define ALGRAPH_H

template <typename T>
class ALGraph
{
public:

    ALGraph(GraphKind kind=DN);
    class ArcNode{
    public:
        int adjvex;
        union{

            char *msg;
            int weight;
        };
        ArcNode *next;
        ArcNode(int adjvex=0,int weight=1,ArcNode *next=nullptr){
            this->adjvex=adjvex;
            this->weight=weight;
            this->next=next;
        }
        ArcNode(int adjvex=0,char *msg=nullptr,ArcNode *next=nullptr){
            this->adjvex=adjvex;
            this->msg=msg;
            this->next=next;

        }

    };
    class VNode{
    public:
        T data;
        ArcNode *firstarc;
        VNode(T data=0,ArcNode *firstarc=nullptr){
            this->data=data;
            this->firstarc=firstarc;
        }
    };
    bool InsertVex(T data);
    bool AddArc(T from,T to,int weight=1){
        this->vertices[Locate(from)].firstarc=new ArcNode(Locate(to),weight,this->vertices[Locate(from)].firstarc);
        arcnum++;
        return true;
    }
    int Locate(T data){
        for(int i=0;i<vexnum;i++){
            if(vertices[i].data==data){
                return i;
            }
        }
        throw "没找到";
        return -1;
    }
    ArcNode *GetAdjArc(T data){
        auto index=Locate(data);
        return vertices[index].firstarc;
    };
    const static int MAXVEX=20;
    VNode vertices[MAXVEX];
    int vexnum,arcnum;
    GraphKind kind;
    void TraverseVex(std::function<void(VNode&)>);
    bool DeleteArc(T from,T to){
        auto temp=vertices[Locate(from)].firstarc;
        ArcNode *pre=nullptr;
        auto toindex=Locate(to);
        while(temp){
            if(temp->adjvex==toindex){
                auto temp2=temp->next;
                delete temp;

                if(pre){
                    pre->next=temp2;
                }else{
                    vertices[Locate(from)].firstarc=temp2;
                }

            }

            pre=temp;
            temp=temp->next;
        }
    }
    ArcNode *FirstAdjVex(int index){
        return vertices[index].firstarc;
    }
    ArcNode *NextAdjVex(ArcNode *pre){
        if(pre!=nullptr){
            return pre->next;
        }
        return nullptr;
    }
    void DFSTraverse(std::function<void(VNode *)> func){
        bool *visited=new bool[vexnum];
        for(int v=0;v<vexnum;v++){
            if(!visited[vexnum]){
                DFS(v,func,visited);
            }
        }
    }
    int GetIndex(VNode *node){
        return (node-vertices);
    }
    void DFS(int index,std::function<void(VNode *)> func,bool *visited){
        visited[index]=true;
        func(vertices+index);
        for(auto v=FirstAdjVex(index);v;v=NextAdjVex(v)){
            if(!visited[index]){
                DFS(v->adjvex,func,visited);
            }
        }
    }
    void BFSTraverse(std::function<void(VNode *)>func){
        bool *visited=new bool[vexnum];
        for(int v=0;v<vexnum;v++){
            if(!visited[vexnum]){
                BFS(v,func,visited);
            }
        }
    }
    void BFS(int index,std::function<void(VNode *)> func,bool *visited){

        QQueue<int> q;
        q.enqueue(index);
        while(!q.empty()){
            if(!visited[index]){
                visited[index]=true;
                auto temp=q.dequeue();
                func(vertices+index);
                for(auto v=FirstAdjVex(temp);v;v=NextAdjVex(v)){
                    if(!visited[index]){
                        q.enqueue(v->adjvex);
                    }
                }
            }
        }
    }
};

#endif // ALGRAPH_H
